package April.存在重复元素III0417;

import java.util.TreeSet;

public class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        int n = nums.length;
        TreeSet<Long> set = new TreeSet<Long>();
        for (int i = 0; i < n; i++) {
            Long ceiling = set.ceiling((long) nums[i] - (long) t);
            if (ceiling != null && ceiling <= (long) nums[i] + (long) t) {
                return true;
            }
            set.add((long) nums[i]);
            if (i >= k) {
                set.remove((long) nums[i - k]);
            }
        }
        return false;

    }
}
/*
* 对于序列中每一个元素 xx 左侧的至多 kk 个元素，如果这 kk 个元素中存在一个元素落在区间 [x - t, x + t][x−t,x+t] 中，我们就找到了一对符合条件的元素。注意到对于两个相邻的元素，它们各自的左侧的 kk 个元素中有 k - 1k−1 个是重合的。于是我们可以使用滑动窗口的思路，维护一个大小为 kk 的滑动窗口，每次遍历到元素 xx 时，滑动窗口中包含元素 xx 前面的最多 kk 个元素，我们检查窗口中是否存在元素落在区间 [x - t, x + t][x−t,x+t] 中即可。

如果使用队列维护滑动窗口内的元素，由于元素是无序的，我们只能对于每个元素都遍历一次队列来检查是否有元素符合条件。如果数组的长度为 nn，则使用队列的时间复杂度为 O(nk)O(nk)，会超出时间限制。

因此我们希望能够找到一个数据结构维护滑动窗口内的元素，该数据结构需要满足以下操作：

支持添加和删除指定元素的操作，否则我们无法维护滑动窗口；

内部元素有序，支持二分查找的操作，这样我们可以快速判断滑动窗口中是否存在元素满足条件，具体而言，对于元素 xx，当我们希望判断滑动窗口中是否存在某个数 yy 落在区间 [x - t, x + t][x−t,x+t] 中，只需要判断滑动窗口中所有大于等于 x - tx−t 的元素中的最小元素是否小于等于 x + tx+t 即可。

我们可以使用有序集合来支持这些操作。

实现方面，我们在有序集合中查找大于等于 x - tx−t 的最小的元素 yy，如果 yy 存在，且 y \leq x + ty≤x+t，我们就找到了一对符合条件的元素。完成检查后，我们将 xx 插入到有序集合中，如果有序集合中元素数量超过了 kk，我们将有序集合中最早被插入的元素删除即可。

注意

如果当前有序集合中存在相同元素，那么此时程序将直接返回 \texttt{true}true。因此本题中的有序集合无需处理相同元素的情况。

为防止整型 \texttt{int}int 溢出，我们既可以使用长整型 \texttt{long}long，也可以对查找区间 [x - t, x + t][x−t,x+t] 进行限制，使其落在 \texttt{int}int 范围内。

*
* */